import java.util.List;

//找出相交的节点
//1.判断有环没环？
//如果有环：
/*1.66型
2.只型
3.口人型*/
/*如果没环：
判断是否能相交
能相交就输出*/
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
public class FindFirstCommonNode {
    //判断是否是有环链表
    private boolean hasCycle(ListNode head){
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=slow){
            if(fast==null||fast.next==null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        if(slow==fast){
            return true;
        }else{
            return false;
        }
    }
    //判断无环链表是否有相交点
    private boolean chkIntersect(ListNode headA, ListNode headB) {
        // write code here
        while (headA.next != null) {
            headA = headA.next;
        }
        while (headB.next != null) {
            headB = headB.next;
        }
        return headA == headB;
    }
    //在无环的情况下返回相交节点
    private ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        while(cur1!=cur2){
            cur1 = cur1==null?head2:cur1.next;
            cur2 = cur2==null?head1:cur2.next;
        }
        return cur1;
    }
    //返回链表中环的入口点
    private ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast){
                break;
            }
        }
        if(slow==fast){
            fast = head;
            while(slow!=fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        return null;

    }
    //有尾结点和两个相交有环链表找相交节点
    private ListNode Find(ListNode head1, ListNode head2, ListNode loop1, ListNode loop2){
        if (head1 == null || head2 == null) {
            return null;
        }
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        if(loop1==loop2) {
            int n = 0;
            while (cur1 != loop1) {
                cur1 = cur1.next;
                n++;
            }
            while (cur2 != loop2) {
                cur2 = cur2.next;
                n--;
            }
            //规定cur1走长的链表
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n > 0) {
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else{
            cur1 = loop1.next;
            while(cur1!=loop1){
                if(cur1==loop2){
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;

        }

    }

    public ListNode chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1){
        if(head1==head2&& head1==null){
            return null;
        }
        //一个有环一个无环一定是没有相交点
        if((hasCycle(head1)&&!hasCycle(head2))||(!hasCycle(head1)&&hasCycle(head2))){
            return null;
        }
        //都有环
        if(hasCycle(head1)&&hasCycle(head2)){
            ListNode loop1 = detectCycle(head1);
            ListNode loop2 = detectCycle(head2);
            if(loop1==loop2){
                return Find(head1,head2,loop1,loop2);
            }else{
                //66型
                if(Find(head1,head2,loop1,loop2)==null){
                    return null;
                }else{
                    return Find(head1,head2,loop1,loop2);
                }
            }

            //都无环
        }else {
            //判断无环是否有相交点？
            if(chkIntersect(head1,head2)){
                return FindFirstCommonNode(head1,head2);
            }else{
                return null;
            }

        }


    }
}
}




